import sys


class Solution:
    # 递归检查 每次递归减1个根节点，最差每轮递归都要遍历所有节点，O(N^2),O(N)
    def verifyPostorder(self, postorder: List[int]) -> bool:
        if len(postorder) < 2:
            return True
        r = postorder[-1]
        i = 0
        while i < len(postorder)-1:
            if postorder[i] > r:
                break
            i += 1
        j = i
        while j < len(postorder)-1:
            if postorder[j] < r:
                return False
            j += 1
        return self.verifyPostorder(postorder[:i]) and self.verifyPostorder(postorder[i:-1])
    
    def verifyPostorder_(self, postorder: List[int]) -> bool:
        def recur(i, j):
            if i >= j:
                return True
            p = i
            while postorder[p] < postorder[j]:
                p += 1
            q = p
            while postorder[p] > postorder[j]:
                p += 1
            return p == j and recur(i, q-1) and recur(q, j-1)
        
        return recur(0, len(postorder)-1)
    
    # 递归构建（合法则删除元素）
    def vp_build(self, postorder: List[int]) -> bool:
        def build(postorder, ma, mi):
            if not postorder: return
            # 最后一个节点在上下界范围？
            var = postorder[-1]
            if not mi < var < ma: return
            postorder.pop()
            # 构建右子树
            build(postorder, ma, var)
            # 构建左子树
            build(postorder, var, mi)
        
        build(postorder, sys.maxsize, -sys.maxsize)
        return not postorder
    
    #TODO 待理解
    def vp_stack(self, postorder: List[int]) -> bool:
        stack = []
        root = float("+inf")
        for i in range(len(postorder)-1, -1, -1):
            if postorder[i] > root: 
                return False
            while stack and stack[-1] > postorder[i]:
                root = stack.pop();
            stack.append(postorder[i])
        return True